# Allocating objects from object caches

A.k.a. Ariadne doesn't like malloc(2), because of potential issues with
fragmentation, compaction, limiting memory usage, syscall filtering,
not-invented-here and wouldn't-this-be-cool-to-use-from-a-signal-handler
(even though that is not -- yet -- supported, it should be doable).

An object cache is a pool of mostly pre-allocated memory, of limited size,
divided into little chunks of constant (for a single cache) size, from which
one can allocate objects and give unused individuals back.

`#include <sHT/resource.h>`

A cache is created with `sHT_alloc_cache` and freed with `sHT_free_cache`.
Objects are allocated from a cache with `sHT_alloc` and freed with `sHT_free`.

These functions are (or will be) defined in `worker/alloc.c`.

The following subsection described how this might *eventually* be implemented.
For now, however, the code only does a single mmap(2).

## Structure

An object cache's memory is divided into the index, page list, the
freelist, all objects and padding, which are, except for the last and first,
allocated consecutively.

(More typical would be to intermix freelists and objects, which would allow
changing the maximum size at run time. But if you *really* want to do that,
you could also just migrate all agents into a new worker. That's the whole
*point* of sHT (or rather, a single point).)

(TODO: improve migration performance by migrate objects by remapping object
pages, instead of copying)

Note the use of the word 'consecutively', instead of contiguously. An object
cache may be spread over multiple, not necessarily adjectant pages.

## Page allocation

We try to use huge pages when possible, to reduce pressure on the TLB, but we
do not insist.

Some pools are very small, so 4KiB may suffice on x86-64 if that's all we need.
Some are rather large, e.g. 10 million IO buffers of 512 bytes each requires
5GiB of memory. Another variable, or rather a constraint, is that virtual
memory may become fragmented.

Some object caches may grow over time, up to a predetermined limit.

To accommodate for variations in size, the preferred page size is taken to
encompass the whole structure. To deal with fragmentation, progressively
smaller page sizes are chosen, so the page size is variable. Not all pages are
allocated from the beginning, so some may be null.

## Freelists

A freelist is a structure that keeps that of objects that are not used anywhere
and can therefore be returned by an allocation routine, provided it is then
removed from the list.

It is conceptually a stack of pointers. The pointers are real, but the stack may
be split over multiple pages.

## Index

The index contains statistics, the element size of the object, a pointer into
the freelist and a list of all pages (possibly split in two halves: allocated
and non-allocated.) It is contiguous.

The number of pages may be variable due to memory fragmentation.
To avoid complexity, the page list, however, allows for the maximal number of
pages (taking in account restrictions imposed by object sizes).
(TODO: there is an oppurtunity for reducing memory usage for the pre-allocated
half.)

The index starts on the first page, and must fit.
(On 64-bit, a 1MiB page list can refer to 65536 pages. If these are each 1MiB
in size, 64GiB can be used for other things. Seems reasonable.)

## Position of these structures within pages

index, freelist and objects, in that order.

No C-object crosses a page boundary. The first C-object in a page starts at
index 0. Other C-objects are placed after the previous, minimising distance
but still having a preferred alignment, *if* it fits within the current page.
If it doesn't fit, it starts on the next page, at index 0.

The code can determine the preferred alignment of each allocated object with
`__alignof__(max_align_t)` when using GCC. (TODO: cache lines, let the last
element end at the end of the page?)

## Legal

Copyright (C) 2018 Ariadne Devos

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
